Избыточный логический вывод и бесконечные циклы |
Страница 2 из 2 Рис. 9.6. Иллюстрация того, что работа программы Prolog зависит от расположения взаимосвязанных выражений: успешное доказательство того, что путь от А до С существует (а); бесконечное дерево доказательства, формируемое из-за того, что выражения находятся в "неправильном " порядке (б) Применение прямого логического вывода при решении задач поиска в графе представляет собой пример динамического программирования, в котором решения подзадач формируются инкрементно из решений меньших подзадач и кэшируются для предотвращения повторного вычисления. Аналогичный эффект в системе обратного логического вывода может быть достигнут с помощью запоминания (memoization), т.е. кэширования решений, найденных для подцелей, по мере их обнаружения, а затем повторного применения этих решений после очередного появления той же подцели, вместо повторения предыдущих вычислений. Этот подход применяется в системах табулированного логического программирования (tabled logic programming), в которых для реализации метода запоминания используются эффективные механизмы сохранения и выборки. В табулированном логическом программировании объединяется целенаправленность обратного логического вывода с эффективностью динамического программирования, присущей прямому логическому выводу. Кроме того, эти системы являются полными применительно к программам в формате Datalog, а это означает, что программисту приходится меньше беспокоиться о бесконечных циклах.
<< В начало < Предыдущая 1 2 Следующая > В конец >> |